package com.platform.modules.alg.alglib.p35;

public class P35 {
    public String output = "";

    private final int maxn = 105;
    private int n;
    private int[] a = new int[maxn];
    // F(i,j) 表示区间 [i，i+2^j-1] 的最值，区间长度为 2^j
    private int F[][] = new int[maxn][maxn];

    void ST_create() {
        for (int i = 1; i <= n; i++)//初始化
            F[i][0] = a[i];
        int k = (int) Math.floor(Math.log(n) / Math.log(2));
        for (int j = 1; j <= k; j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)//n-2^j+1
                F[i][j] = Math.max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
    }

    int ST_query(int l, int r) // 求区间[l..r]的最值
    {
        int k = (int) Math.floor(Math.log(r - l + 1) / Math.log(2));
        return Math.max(F[l][k], F[r - (1 << k) + 1][k]); // 取两个区间最值
    }

    void ST_print() {
        int k = (int) Math.floor(Math.log(n) / Math.log(2));
        for (int j = 0; j <= k; j++) {
            for (int i = 1; i <= n - (1 << j) + 1; i++) // n-2^j+1,打印第一列
                output += F[i][j] + " ";
            output += "\n";
        }
    }

    public String cal(String input) {
        int l, r;
        int i, v;

        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);

        String[] words = line[1].split(" ");

        // 5 3 7 2 12 1 6 4 8 15
        for (i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(words[i - 1]);
        }

        ST_create();//创建ST表
        ST_print();

        String[] bounds = line[2].split(" ");
        l = Integer.parseInt(bounds[0]);
        r = Integer.parseInt(bounds[1]);
        // 求区间[l..r]的最值
        output += "" + ST_query(l, r);
        return output;
    }
}
